\section{Traditional Garbage Collection}
\begin{frame}{Garbage Collection in JAVA}
\begin{itemize}
\item Garbage collection in JAVA is executed by a deamon thread called the Garbage Collector. \pause
\item GC is initialized depending on de Java heap size. \pause
\item GC in JAVA is rather complex.
\end{itemize}
\end{frame}

\begin{frame}{The Heap in Graph Representation}
\begin{itemize}
\item Languages that disallow pointer arithmetic (Java, C\#) store objects in an internal array. \pause
\item Objects can only be reached via referencing. \pause
\item We can create a graph of object references called an \it{Object Graph} or \it{Heap Graph}.
\end{itemize}
\end{frame}

\begin{frame}{Naive Mark and Sweep}
\begin{itemize}
\item Each Object on the heap has a flag reserverd for GC. \pause
\item Initially all the flag of each object is \emph{cleared}. \pause
\item Every object which is pointed to is flagged \emph{in use}. \pause
\item Finally the memory of every object not marked \emph{in use} is freed. \pause
\item GC flags of all objects are cleared.
\end{itemize}
\end{frame}

\begin{frame}{Naive Mark and Sweep}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [right of=S, fill=green] {$v_0$};
  \node[state] (v1) [below of=S] {$v_1$};
  \node[state] (v2) [right of=v1] {$v_2$};
  \node[state] (v3) [right of=v2] {$v_3$};
  \node[state] (v4) [below of=v1] {$v_4$};
  \node[state] (v5) [right of=v4] {$v_5$};
  \node[state] (v6) [right of=v5] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v5)
    (v3) edge (v6)
    (v6) edge (v3)
  ;
\end{tikzpicture} 
\end{figure}
\end{frame}

\begin{frame}{Naive Mark and Sweep}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [right of=S, fill=green] {$v_0$};
  \node[state] (v1) [below of=S, fill=green] {$v_1$};
  \node[state] (v2) [right of=v1] {$v_2$};
  \node[state] (v3) [right of=v2] {$v_3$};
  \node[state] (v4) [below of=v1] {$v_4$};
  \node[state] (v5) [right of=v4] {$v_5$};
  \node[state] (v6) [right of=v5] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v5)
    (v3) edge (v6)
    (v6) edge (v3)
  ;
\end{tikzpicture} 
\end{figure}
\end{frame}

\begin{frame}{Naive Mark and Sweep}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [right of=S, fill=green] {$v_0$};
  \node[state] (v1) [below of=S, fill=green] {$v_1$};
  \node[state] (v2) [right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [right of=v2] {$v_3$};
  \node[state] (v4) [below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [right of=v4] {$v_5$};
  \node[state] (v6) [right of=v5] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v5)
    (v3) edge (v6)
    (v6) edge (v3)
  ;
\end{tikzpicture} 
\end{figure}
\end{frame}

\begin{frame}{Naive Mark and Sweep}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [right of=S, fill=green] {$v_0$};
  \node[state] (v1) [below of=S, fill=green] {$v_1$};
  \node[state] (v2) [right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [right of=v2] {$v_3$};
  \node[state] (v4) [below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [right of=v4, fill=green] {$v_5$};
  \node[state] (v6) [right of=v5] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v5)
    (v3) edge (v6)
    (v6) edge (v3)
  ;
\end{tikzpicture} 
\end{figure}
\end{frame}

\begin{frame}{Naive Mark and Sweep}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [right of=S, fill=green] {$v_0$};
  \node[state] (v1) [below of=S, fill=green] {$v_1$};
  \node[state] (v2) [right of=v1, fill=green] {$v_2$};
  \node[state] (v3) [right of=v2, fill=red] {$v_3$};
  \node[state] (v4) [below of=v1, fill=green] {$v_4$};
  \node[state] (v5) [right of=v4, fill=green] {$v_5$};
  \node[state] (v6) [right of=v5, fill=red] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v5)
    (v3) edge (v6)
    (v6) edge (v3)
  ;
\end{tikzpicture} 
\end{figure}
\end{frame}

\begin{frame}{Reference Counting}
\begin{itemize}
\item Tracking the amount of references to an object. \pause
\item When the amount of references becomes zero, the object can be deallocated. \pause
\item Reference Counting algorithms require detection of disconnected cycles!
\end{itemize}
\end{frame}

\begin{frame}{Reference Counting}
\begin{figure}
\begin{tikzpicture}[->,>=stealth', node distance=1.5cm]
  \node (S)                    {};
  \node[state] (v0) [right of=S] {$v_0$};
  \node[state] (v1) [below of=S] {$v_1$};
  \node[state] (v2) [right of=v1] {$v_2$};
  \node[state] (v3) [right of=v2] {$v_3$};
  \node[state] (v4) [below of=v1] {$v_4$};
  \node[state] (v5) [right of=v4, fill=red] {$v_5$};
  \node[state] (v6) [right of=v5] {$v_6$};

  \path
    (S) edge (v0)
    (v0) edge (v1)
    (v1) edge (v2)
    (v1) edge (v4)
    (v2) edge (v4)
    (v3) edge (v6)
    (v6) edge (v3)
  ;
\end{tikzpicture} 
\end{figure}
\end{frame}